package com.celan.year2023.month05.day14;


import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @author Celan
 * @description TODO
 */
class Solution {

    public int[] rearrangeBarcodes(int[] barcodes) {
        int n = barcodes.length;
        int[] res = new int[n];

        //记录各条形码出现次数
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int barcode : barcodes) {
            map.put(barcode, map.getOrDefault(barcode, 0) + 1);
        }
        //最大堆排序,根据出现频率排序
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        map.forEach((barcode, occurs) -> queue.offer(new int[]{barcode, occurs}));

        for (int i = 0; i < n; ++i) {
            //从最大堆拉取一个出现频率最多的条形码
            int[] poll1 = queue.poll();
            int barcode1 = poll1[0], occurs1 = poll1[1];
            if (i > 0 && res[i - 1] == barcode1) {
                //如果和最后一个条形码相等,则拉取第二多的
                int[] poll2 = queue.poll();
                int barcode2 = poll2[0], occurs2 = poll2[1];
                res[i] = barcode2;
                queue.offer(new int[]{barcode1, occurs1});
                queue.offer(new int[]{barcode2, occurs2 - 1});
            } else {
                res[i] = barcode1;
                queue.offer(new int[]{barcode1, occurs1 - 1});
            }
        }

        return res;
    }

}
